package middle;

public class Solution_331 {

    public static void main(String[] args) {
        Solution_331 model = new Solution_331();
        System.out.println(model.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#")); // true
        System.out.println(model.isValidSerialization("1,#")); // false
        System.out.println(model.isValidSerialization("9,#,#,1")); // false
        System.out.println(model.isValidSerialization("9,#,1,#,#")); // true
        System.out.println(model.isValidSerialization("#")); // true
    }

    private int index = 0;
    public boolean isValidSerialization(String preorder) {
        index = 0;
        String[] array = preorder.split(",");
        return dps(array) && index == array.length;
    }

    private boolean dps(String[] chars) {
        if (index >= chars.length) {
            return false;
        }
        if (chars[index++].equals("#")) {
            return true;
        } else {
            boolean left = dps(chars);
            boolean right = dps(chars);
            return left && right;
        }
    }
}
